package sort.selectsort;

/**
 * 选择排序
 * 算法步驟
 * <p>
 * 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
 * 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
 * 重复第2步，直到所有元素均排序完毕。
 *
 * @author xushijian
 * @date 2021/12/29 15:17
 */
public class SelectSort {

    public static void main(String[] args) {
        int[] arr = {5, 2, 1, 90, 2, 17, 0, 41, 7, 1000};

        selectSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }

    }

    /**
     * 核心点：使用的是标记索引
     * <p>
     * 与插入法比较： 遍历过程相反，插入法：向前遍历比较； 选择排序：先后遍历，选取最小或最大值
     *
     * @param arr 数组
     */
    public static void selectSort(int[] arr) {

        if (arr == null || arr.length <= 1) {
            return;
        }
        int len = arr.length, minVal, tmp;
        for (int i = 0; i < len; i++) {
            minVal = i;
            for (int j = i; j < len; j++) {
                if (arr[j] < arr[minVal]) {
                    minVal = j;
                }
            }
            //不相等表示存在交换
            if (minVal != i) {
                tmp = arr[minVal];
                arr[minVal] = arr[i];
                arr[i] = tmp;
            }
        }
    }
}